package momo.multitree.algo;

import momo.multitree.structure.*;

import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.Set;

import org.apache.commons.logging.Log;
import org.apache.commons.logging.LogFactory;


public abstract class ModifiedDijkstra
{	
	
	private Log log = LogFactory.getLog(ModifiedDijkstra.class);
	
	protected Tree optimumTree(Graph graph, Node root)
	{
		Tree tree = new Tree(root);
		LinkedHashMap<String, Edge> edges = new LinkedHashMap<String, Edge>();
		
		// S = {};
		LinkedHashSet<Node> S = new LinkedHashSet<Node>();
		// E = {};
		LinkedHashSet<Edge> Et = new LinkedHashSet<Edge>();
		// pred = {};
		LinkedHashMap<Node, Node> pred = new LinkedHashMap<Node, Node>();
		// Q = {r};
		LinkedHashSet<Node> Q = new LinkedHashSet<Node>();
		Q.add(root);
//		log.info("Root: " + root);
		// L(r) = 0;
		LinkedHashMap<Node, Double> L = new LinkedHashMap<Node, Double>();
		L.put(root, 0d);
		
		// while Q != 0
		while ( !Q.isEmpty() )
		{
			// v = min L(u) where u E Q
			Node v = min(Q, L);
//			log.info("min(Q,L): " + v.getId());
//			log.debug("Node v: " + v.getId());
			// S = S U {v};
			S.add(v);
//			log.info("S add " + v.getId());
			// if pred (v) != null then Et = Et U { pred(v), v};
			if ( pred.get(v) != null )
			{
//				log.info("Edge added into Et: " + edges.get(pred.get(v).getId()+","+v.getId()).toString() );
				Et.add( edges.get(pred.get(v).getId()+","+v.getId()) );
//				tree.add( edges.get(pred.get(v).getId()+""+v.getId()) );
			}
			// Q = Q - {v} U adj(v);
			Q.remove(v);
//			log.info("Q remove " + v.getId());
			for ( Edge e: graph.getEdgesOfNode(v) )
			{
				Node adjV = e.nextNode(v);
				if ( !S.contains(adjV) )
				{
					Q.add(adjV);
				}
			}
			
//			StringBuffer buffer = new StringBuffer();
//			for(Node nn : Q)
//				buffer.append(nn.getId()+",");
//			log.info("Q: " + buffer.toString());
			
			
			// foreach u E Q do L(u) = infinite
			for( Node u: Q )
				L.remove(u);
			
//			buffer = new StringBuffer();
//			for(Node nn : L.keySet())
//				buffer.append(nn.getId()+",");
//			log.info("L: " + buffer.toString());
			
			//foreach w E S do
			//	foreach u E adj(w), u !E S do
			//		l = L ( S U {u}, Et U (w,u) );
			//		if l < L(u) then L(u) = l; pred(u) = w;
			for( Node w: S )
			{
//				log.info("Node w of S: " + w.getId());
				for ( Edge e: graph.getEdgesOfNode(w) )
				{
					Node u = e.nextNode(w);
					if ( !S.contains(u) )
					{
						double l = calObjCost(S, u, Et, e, L);
//						log.info(" w->u "+w.getId()+"->"+u.getId()+" l: "+l);
						if ( L.get(u) == null || l < L.get(u))
						{
//							log.info("L("+u.getId()+")="+l);
							L.put(u, l);
							pred.put(u, w);
							edges.put(w.getId()+","+u.getId(), e);
						}
					}
				}
			}
		}
		
		for(Edge edge: Et)
			tree.add(edge);
		
		return tree;
	}
	
	private Node min(LinkedHashSet<Node> Q, LinkedHashMap<Node, Double> L)
	{
		Node[] nodes = Q.toArray(new Node[0]);
		if ( nodes.length == 1 )
			return nodes[0];
		
		Node retNode = nodes[0];
		for(int i=1; i<nodes.length; i++)
			if ( L.get(nodes[i]) < L.get(retNode) )
				retNode = nodes[i];
		return retNode;
	}
	
	abstract public double calObjCost(LinkedHashSet<Node> S, Node node, 
			LinkedHashSet<Edge> Et, Edge edgeToAdd, LinkedHashMap<Node, Double> labels);	
}//end of class ModifiedDijkstra
